package Matrix;

import java.util.Arrays;

/**
 * question: 求一个矩阵的子矩阵中，元素和最大的矩阵的元素和
 * example:
 * 1, 2, 3,-4  ->  1,2,3 -> 6
 * -1,-2,-3,-4
 * <p>
 * -5, 3, 6,  4  -> 3,6,4   -> 14
 * -7, 9,-5,  3     9,-5,3
 * -10,1,-200,4
 *
 * @author Liaorun
 */
public class SubMatrixMaxSum {

    public static void main(String[] args) {
        System.out.println(maxSum(new int[][]{{1, 2, 3, -4}, {1, 2, 3, -4}}));
    }

    public static int maxSum(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;
        int cur;
        int[] s;


        // 矩阵的压缩数组
        s = new int[m[0].length];

        for (int i = 0; i < m.length; i++) {

            // 清空压缩数组的值，因为起始行 变更了
            Arrays.fill(s, 0);

            for (int j = i; j < m.length; j++) {
                // 结束的行号j,i~j行是我讨论的范围
                // j 的变大，表示矩阵的宽度变大，
                cur = 0;
                for (int k = 0; k < s.length; k++) {
                    // 遍历每一行的时候，结束都没有清空s压缩数组的值，这样才能保留上一行的数值
                    // 把当前行的值加到压缩数组中
                    s[k] += m[j][k];
                    cur += s[k];
                    // 检查是否可以刷新最好的情况
                    max = Math.max(max, cur);
                    // cur 变成负数，表示前面一段的连续子数组带了的收益为负
                    // 最好的结果不能考虑前面的数字
                    cur = Math.max(cur, 0);
                }
            }
        }

        return max;
    }
}
